/**
 *  斐波那契数列： 
 *     1、1、2、3、5、8、
 *  给定整数N，求返回斐波那契数列的第N项
 * 
 * 
 *  具体题目：
 *  sec1：
 *      母牛每年生一只母牛，新出生的母牛成长三年后也能每年生一只母牛，假设不会死。
 *      求N年后，母牛的数量。
 *      1   2   3   4       5
 *      A   A   A   A       A
 *          B   B   B+B1    B+B1+B2
 *              C   C       C+C1
 *                  D       D
 *                          E
 *                          
 * 数列：1   2   3  |4       6
 *      F(N) = F(N-1)+F(N-3)
 *              去年的牛    三年前的牛，可新产牛啦
 * 
 * 数列：1   2   3  |4       6
 *      ppre pre res    
 */                 


 function cow1(n){
    if(n===1||n===2||n===3){
        return n;
    }
    return cow1(n-1)+cow1(n-3);
}

//非递归
function cow2(n){
    if(n<1){
        return 0;
    }
    if(n===1||n===2||n===3){
        return n;
    }

    let res = 3,
        pre = 2,
        ppre = 1;
    for(let i = 4;i<=n;i++){
        let temp1 = res;
        let temp2 = pre;
        res = res + ppre;
        pre = temp1;
        ppre = temp2;
    }
    return res;
}






// step1: 进阶----假如每头母牛只能存活十年
// ===> F(N) = F(N-1) + F(N-3) - F(N-10)


/*****
 * sec2:
 *      爬楼梯：给定整数N，代表台阶数，一次可以跨2 or 1个台阶，返回共有多少种走法
 * 如1 ==》 1
 *      1
 *   2 ==》 2
 *      1+1 2
 *   3 ==》 3
 *      1+1+1 2+1 1+2 
 *   4 ==》 
 *      1+1+1+1 2+2 1+1+2 1+2+1 2+1+1
 * 可得当前方式依赖于前一种方案
 * 或者从规律也可看到
 *     1、2、3、5...
 * F(N) = F(N-1)  + F(N-2)
 * ===> 
 *      当台阶有N阶，最后跳到N阶的情况只能是：（因为每步只能走1 or 2步）
 *      1、从N-1阶直接跨一级 
 *      2、从N-2阶跨两级
 * 
 * 我们由暴力递归可得到 O(2^N)复杂度的解法。 
 * O(N)方法则是 递归转DP，顺序计算 充分利用依赖关系
 * O(logN) ===》 矩阵乘法求解斐波拉契数列
 */